﻿#include "Tree.h"
#include "Queue.h"
BT* BuyNode(BT* Node,int x) {
	BT* NewNode = (BT*)malloc(sizeof(BT));
	if (NewNode == NULL) {
		perror("malloc fail");
		exit(1);
	}
	Node = NewNode;
	Node->root = x;
	Node->LeftChild = Node->RightChild = NULL;
	return Node;
}
BT* CreatNode(BT* Node) {
	BT* Node1 = BuyNode(Node, 1);
	BT* Node2 = BuyNode(Node, 2);
	BT* Node3 = BuyNode(Node, 3);
	BT* Node4 = BuyNode(Node, 4);
	BT* Node5 = BuyNode(Node, 5);
	Node1->LeftChild = Node2;
	Node1->RightChild = Node3;
	Node2->LeftChild = Node4;
	Node4->LeftChild = Node5;
	return Node1;
}
//前序遍历(根 左 右）
void Preorder(BT* Node) {
	if (Node == NULL) {
		return;
	}
	printf("%d ", Node->root);
	Preorder(Node->LeftChild);
	Preorder(Node->RightChild);
}

//中序遍历(左 根 右）4 2 1 3
void Inorder(BT* Node) {
	if (Node == NULL) {
		return;
	}
	Inorder(Node->LeftChild);
	printf("%d ", Node->root);
	Inorder(Node->RightChild);
}
//后序  （左 右 根）4 2 3 1
void Postorder(BT* Node) {
	if (Node == NULL) {
		return;
	}
	Postorder(Node->LeftChild);
	Postorder(Node->RightChild);
	printf("%d ", Node->root);
}
//⼆叉树结点个数(按中序遍历)
int BinaryTreeSize(BT* Node) {
	if (Node == NULL) {
		return 0;
	}
	return 1 + BinaryTreeSize(Node->LeftChild) + BinaryTreeSize(Node->RightChild);
}
// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BT* Node) {
	if (Node == NULL) {
		return 0;
	}
	if (Node->LeftChild == NULL && Node->RightChild == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(Node->LeftChild) + BinaryTreeLeafSize(Node->RightChild);
}
// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BT* Node, int k) {
	if (Node == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return BinaryTreeLevelKSize(Node->LeftChild, k - 1) + BinaryTreeLevelKSize(Node->RightChild, k - 1);
}
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BT* Node) {
	if (Node == NULL) {
		return 0;
	}
	int left = BinaryTreeDepth(Node->LeftChild);
	int right = BinaryTreeDepth(Node->RightChild);
	return 1 + (left > right ? left : right);
}

// ⼆叉树查找值为x的结点 
BT* BinaryTreeFind(BT* Node, BTDataType x) {
	if (Node == NULL) {
		return NULL;//必须要加NULL！
	}
	if (Node->root == x) {//找到就返回结点
		return Node;
	}
	//没找到继续遍历
	BT* LeftChlid = BinaryTreeFind(Node->LeftChild,x);
	if (LeftChlid) {
		return LeftChlid;
	}

	BT* RightChlid = BinaryTreeFind(Node->RightChild,x);
	if (RightChlid) {
		return RightChlid;
	}
	//左右孩子都没找到
	return NULL;
}

// ⼆叉树销毁
void BinaryTreeDestory(BT** Node) {
	if (*Node == NULL){
		return;
	}
	BinaryTreeDestory(&((*Node)->LeftChild));
	BinaryTreeDestory(&((*Node)->RightChild));
	free(*Node);
	*Node = NULL;
}

// 层序遍历
void LevelOrder(BT* Node) {
	Queue q;
	//新建一个队列
	QueueInit(&q);
	//取树顶数据进队

	QueuePush(&q, Node);
	//取队里的结点 结点有左or右孩子 结点出队 左右孩子进队
	while (!QueueEmpty(&q)) {
		//取队头并打印
		BT* Front = QueueFront(&q);
		printf("%d ", Front->root);

		//判断对头左右子树是否为空
		if(Front->LeftChild)
			QueuePush(&q, Front->LeftChild);
		if(Front->RightChild)
			QueuePush(&q, Front->RightChild);
		//出队列
		QueuePop(&q);
		
	}
	
}


// 判断是否为完全二叉树
bool BinaryTreeComplete(BT* Node) {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, Node);//取树顶入队
	while (!QueueEmpty(&q)) {
		BT*Top= QueueFront(&q);
		if (Top == NULL) {
			break;
		}
		
		QueuePush(&q, Top->LeftChild);
		QueuePush(&q, Top->RightChild);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q)) {
		BT* Top = QueueFront(&q);
		QueuePop(&q);
		if (Top != NULL) {
			QueueDestroy(&q);
			return false;
		}
		//QueuePop(&q);
	}
	QueueDestroy(&q);
	return true;
}